\chapter{Revisão da literatura}
  
\cite{arguelo1997} apresenta um algoritmo, baseado no GRASP, para reconstruir
trilhos de aeronaves que tenham sofrido modificações durante o decorrer do dia.

Para isso ele usa uma função de avaliação gulosa e um método de seleção
aleatório que de forma iterativa tenta construir uma solução viável, a
solução inicial é utilizada como entrada e então é viabilizada através desses
movimentos. Note que se a solução inicial ainda for válida, a fase de construção
se torna desnecessária. 

Em cada iteração os movimentos possíveis são gerados e
avaliados. Os mais promissores são armazenados na lista restrita de candidatos
(LRC) na qual uma é selecionada aleatoriamente. A LCR pode ser restringida por
quantidade ou por qualidade. Por exemplo, os melhores $X$ movimentos ou todos os
movimentos com $Y$\% do melhor movimento podem ser armazenados na LRC.
Esse processo é repetido até que uma solução válida seja obtida. Isto
representa uma iteração. A vantagem de usar a solução inicial é que ela é
próxima a malha aérea planejada inicialmente pela companhia. 

A fase de busca local usa a solução da fase de construção para encontrar um
mínimo local. Essa fase usa procedimentos de trocas determinísticas para
atingir o mínimo local. 

A vizinhança definida inclui a criação de um novo  conjunto de trilhos em que os
voos que forem alocados a eles serão cancelados. Três são as operações usadas
para gerar novos vizinhos: \textit{flight route augmentation}, \textit{partial
route exchange}, e \textit{simple circuit cancellation}. Os dois primeiros são
aplicados em um par de trilhos e o terceiro é aplicado em um único trilho. 

O \textit{flight route augmentation} opera removendo um voo ou uma sequência de
voos de um dos trilhos e adicionando esses voos no outro. O trilho de destino é
aumentado dos voos removidos do trilho de origem. O trilho de destino pode ser
aumentado de três formas distintas. Primeiro, um circuito pode ser colocado no
seu início. Um circuito é uma sequência de voos que inicia e termina no mesmo
aeroporto. Uma segunda forma é inserir o circuito em algum lugar entre o
primeiro e o último voo do trilho de destino. A terceira forma permite alterar
o aeroporto de destino, ou seja, insere uma sequência de voos no trilho de destino. 

O \textit{partial route exchange} opera simplesmente trocando um par de
sequências de voos entre dois trilhos e o \textit{simple circuit cancelation}
remove um circuito de um trilho e cria um trilho de cancelamento. 

Os testes realizados no artigo foram feitos em uma instância cedida pela
Continental Airlines, referente a frota 757, com 42 voos operados por 16
aeronaves em uma rede de 13 aeroportos espalhados por 3 continentes. A malha
não foi disponibilizada no artigo.

		
\cite{mercier2007} desenvolveram um modelo matemático que permite resolver de
forma integrada a construção de trilhos de aeronaves e a escala de tripulantes
permitindo mudanças nos horários dos voos. A ligação entre as restrições desses
dois problemas garante que o mesmo planejamento seja feito para os trilhos das
aeronaves e para a escala dos tripulantes, permitindo assim a redução de custos
pela antecipação de problemas das etapas futuras. Por outro lado essa abordagem
aumenta a complexidade na resolução desses problemas. Com a agregação desses
dois problemas a resolução se tornou pesada e viável apenas para instâncias
diárias. Os testes do algoritmo foram baseados em instâncias contendo no máximo
500 voos que foram fornecidas por duas grandes companhias aereas, os dados
dessas instâncias não se encontram disponíveis no artigo.

\cite{cordeau2001}, \cite{klabjan2002} e \cite{mainville2003} mostraram em seus
trabalhos que a resolução desses problemas de forma integrada podem gerar
soluções que são significativamente melhores que as obtidas pela resolução
sequencial.

  		
Pontes R., et al \cite{pontes2002} utilizaram a fase de construção do GRASP
para resolver o PCTA, também propuseram um modelo matemático que foi
adaptado para auxiliar na geração da nossa solução. Além disso, uma instância
da Rio-Sul foi disponibilizada para a realização de testes. Com o solver eles
conseguiram obter a solução ótima dessa instância mas o autor informou que
essa resolução demorou dias para finalizar. Com a utilização da heurística
eles conseguiram apenas se aproximar dessa solução porém com um tempo de 384
segundos. 
		
Em \cite{mohamed2011} Mohamed et al. resolveu de forma integrada o problema
de atribuição de frota e o problema de construção de trilhos de aeronaves,
para uma pequena empresa de aviação a TunisAir. Além disso as restrições de
manutenção não foram levadas em consideração pelo fato dela poder ser feita
em todos os aeroportos em que as aeronaves passam a noite.
		
%GRASPs have been used to find high quality solutions to a variety of logistics and combi- natorial optimization problems including maintenance base %planning (Feo and Bard, 1989), machine scheduling (Feo et al., 1991), and number partitioning (Argu ̈ello et al., 1996) to name a few.
%ão
 